package com.mlh.dp.old;
//给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：
// 将 '0' 在字符串末尾添加 zero 次。
// 将 '1' 在字符串末尾添加 one 次。
// 以上操作可以执行任意次。
// 如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。
// 请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 10^9 + 7 取余 后返回。
//
// 输入：low = 3, high = 3, zero = 1, one = 1
// 输出：8
// 解释：
// 一个可能的好字符串是 "011" 。
// 可以这样构造得到："" -> "0" -> "01" -> "011" 。
// 从 "000" 到 "111" 之间所有的二进制字符串都是好字符串。

public class CountGoodStrings {
    public static void main(String[] args) {
        System.out.println(method1(200,200,10,1));
    }

    //该题是自己写出的
    //这题没什么难点  就是爬楼梯
    //就是边界条件要设置好
    public static int method1(int low, int high, int zero, int one) {
        int[]dp=new int[high+1];//数组含义：low=high=i时，满足要求的好字符串的数量
        int temp=1000000007;
        //初始化边界条件
        if(zero>one){
            for(int i=one;i<=zero;i+=one){
               dp[i]=1;
            }
            dp[zero]++;
            //状态转移
            for(int i=zero+1;i<=high;i++){
               dp[i]=(dp[i-zero]+dp[i-one])%temp;
            }
        }else if(zero<one){
            for(int i=zero;i<=one;i+=zero){
                dp[i]=1;
            }
            dp[one]++;
            //状态转移
            for(int i=one+1;i<=high;i++){
                dp[i]=(dp[i-zero]+dp[i-one])%temp;
            }
        }else{
            dp[one]=2;
            //状态转移
            for(int i=one+1;i<=high;i++){
                dp[i]=(dp[i-zero]+dp[i-one])%temp;
            }
        }
        int res=0;
        for(int i=low;i<=high;i++){
            res+=dp[i];
            res=res%temp;
        }
        //System.out.println(Arrays.toString(dp));
        return res;
    }
}
